/**
 * @file knapsack_problem.cpp
 * @author Wang Bo (1276106221@qq.com)
 * @brief 
 * 问题：在10件物品中，选择一定数量的物品放入背包
 * 背包的最大容量为25个单位的w，要求val最高
 * 思路：以val/w的比率作为贪心策略
 * 注意：问题中的物品可以分割
 * @version 0.1
 * @date 2021-07-07
 * 
 * @copyright Copyright (c) 2021
 * 
 */
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <random>
using std::cout;
using std::endl;
using std::vector;
using std::string;

template <typename W, typename V, typename F>
struct Object {
    W weight;
    V value;
    F valuePerWeight;
    inline bool operator<(const Object<W, V, F>& that) const {
        return valuePerWeight < that.valuePerWeight;
    }
    inline bool operator>(const Object<W, V, F>& that) const {
        return !operator<(that) && !operator==(that);
    }
    inline bool operator==(const Object<W, V, F>& that) const {
        return valuePerWeight == that.valuePerWeight;
    }
    operator double() {
        return value;
    }
    friend std::ostream& operator<<(std::ostream& os, const Object<W, V, F>& obj) {
        os << "Value: " << obj.value
           << "\tWeight: " << obj.weight
           << "\tValue/UnitWeight: " << obj.valuePerWeight;
        return os;
    }
};

template <typename W, typename V, typename F>
auto fillKnapsack(vector<Object<W, V, F>>& objs, W knapsackCapacity) {
    vector<Object<W, V, F>> knapsackContents;
    std::sort(objs.begin(), objs.end(), std::greater<Object<W, V, F>>());
    auto curObj = objs.begin();
    W curTotalWeight = 0;
    while (curTotalWeight <= knapsackCapacity) {
        knapsackContents.push_back(*curObj);
        curTotalWeight += curObj->weight;
        ++curObj;
    }
    auto lastObjWeightToRemove = curTotalWeight - knapsackCapacity;
    knapsackContents.back().weight -= lastObjWeightToRemove;
    knapsackContents.back().value -= knapsackContents.back().valuePerWeight * lastObjWeightToRemove;
    return knapsackContents;
}

void testSolution(uint32_t objNums, double knapsackCapacity) {
    using W = double;
    using V = double;
    using F = double;
    std::random_device rd;
    std::mt19937 rand(rd());
    std::uniform_int_distribution<std::mt19937::result_type> dist(1, objNums);
    vector<Object<W, V, F>> objs(objNums);
    std::for_each(objs.begin(), objs.end(), [&](auto& x){
        auto weight = static_cast<W>(dist(rand));
        auto value = static_cast<V>(dist(rand));
        x = Object<W, V, F> {weight, value, value/weight};
    });
    cout << "Objects abvailable:\n";
    std::for_each(objs.begin(), objs.end(), [](const auto& obj){
        cout << obj << endl;
    });
    auto solution = fillKnapsack(objs, knapsackCapacity);
    cout << "Objects selected to be in the knapsack:\n"
         << "max capacity = " << knapsackCapacity << endl;
    std::for_each(solution.begin(), solution.end(), [](const auto& obj){
        cout << obj << endl;
    });
    auto totalValue = std::accumulate(solution.begin(), solution.end(), 0.0, std::plus<double>());
    cout << "total value: " << totalValue << endl;
}

int main(int argc, const char** argv) {
    testSolution(10, 25);
    return 0;
}